{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #环形闯关游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #union-find #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #并查集 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: ringGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #环形闯关游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "「力扣挑战赛」中有一个由 `N` 个关卡组成的**环形**闯关游戏，关卡编号为 `0`~`N-1`，编号 `0` 的关卡和编号 `N-1` 的关卡相邻。每个关卡均有积分要求，`challenge[i]` 表示挑战编号 `i` 的关卡最少需要拥有的积分。\n",
    "![图片.png](https://pic.leetcode-cn.com/1630392170-ucncVS-%E5%9B%BE%E7%89%87.png){:width=\"240px\"}\n",
    "\n",
    "\n",
    "小扣想要挑战关卡，闯关具体规则如下：\n",
    "\n",
    "- 初始小扣可以指定其中一个关卡为「开启」状态，其余关卡将处于「未开启」状态。\n",
    "- 小扣可以挑战处于「开启」状态且**满足最少积分要求**的关卡，若小扣挑战该关卡前积分为 `score`，挑战结束后，积分将增长为 `score|challenge[i]`（即位运算中的 `\"OR\"` 运算）\n",
    "- 在挑战某个关卡后，该关卡两侧相邻的关卡将会开启（若之前未开启）\n",
    "\n",
    "请帮助小扣进行计算，初始最少需要多少积分，可以挑战 **环形闯关游戏** 的所有关卡。\n",
    "\n",
    "**示例1：**\n",
    "\n",
    "> 输入：`challenge = [5,4,6,2,7]`\n",
    ">\n",
    "> 输出：`4`\n",
    "> \n",
    "> 解释： 初始选择编号 3 的关卡开启，积分为 4\n",
    ">挑战编号 3 的关卡，积分变为 $4 | 2 = 6$，开启 2、4 处的关卡\n",
    ">挑战编号 2 的关卡，积分变为 $6 | 6 = 6$，开启 1 处的关卡\n",
    ">挑战编号 1 的关卡，积分变为 $6 | 4 = 6$，开启 0 处的关卡\n",
    ">挑战编号 0 的关卡，积分变为 $6 | 5 = 7$\n",
    ">挑战编号 4 的关卡，顺利完成全部的关卡\n",
    "\n",
    "\n",
    "**示例2：**\n",
    "\n",
    "> 输入：`challenge = [12,7,11,3,9]`\n",
    ">\n",
    "> 输出：`8`\n",
    ">\n",
    "> 解释： 初始选择编号 3 的关卡开启，积分为 8\n",
    ">挑战编号 3 的关卡，积分变为 $8 | 3 = 11$，开启 2、4 处的关卡\n",
    ">挑战编号 2 的关卡，积分变为 $11 | 11 = 11$，开启 1 处的关卡\n",
    ">挑战编号 4 的关卡，积分变为 $11 | 9 = 11$，开启 0 处的关卡\n",
    ">挑战编号 1 的关卡，积分变为 $11 | 7 = 15$\n",
    ">挑战编号 0 的关卡，顺利完成全部的关卡\n",
    "\n",
    "**示例3：**\n",
    "\n",
    "> 输入：`challenge = [1,1,1]`\n",
    ">\n",
    "> 输出：`1`\n",
    "\n",
    "**提示：** \n",
    "- `1 <= challenge.length <= 5*10^4`\n",
    "- `1 <= challenge[i] <= 10^14`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [K8GULz](https://leetcode.cn/problems/K8GULz/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [K8GULz](https://leetcode.cn/problems/K8GULz/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,6,2,7]', '[1,17,1,19,1]', '[12,7,11,3,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef ringGame(self, challenge):\n",
    "\t\tmx = max(challenge)\n",
    "\t\tfor start, num in enumerate(challenge):\n",
    "\t\t\tif num == mx:\n",
    "\t\t\t\tbreak\n",
    "\t\tarr = challenge[start + 1:] + challenge[:start + 1]\n",
    "\t\tbase = 1\n",
    "\t\twhile base << 1 <= mx:\n",
    "\t\t\tbase <<= 1\n",
    "\t\tans = base\n",
    "\t\tbase >>= 1\n",
    "\t\twhile base:\n",
    "\t\t\tif self.chk(arr, mx, ans + base - 1) == False:\n",
    "\t\t\t\tans += base\n",
    "\t\t\tbase >>= 1\n",
    "\t\treturn ans + base\n",
    "\t\n",
    "\tdef chk(self, arr, mx, x):\n",
    "\t\tcur = x\n",
    "\t\tstack = [[mx * 2, 0], [mx, 0]]\n",
    "\t\tfor num in arr:\n",
    "\t\t\tif cur >= num:\n",
    "\t\t\t\tcur |= num\n",
    "\t\t\telse:\n",
    "\t\t\t\tstack.append([num, cur])\n",
    "\t\t\t\tcur = x\n",
    "\t\t\twhile cur >= stack[-1][0]:\n",
    "\t\t\t\tcur |= stack[-1][0] | stack[-1][1]\n",
    "\t\t\t\tstack.pop()\n",
    "\t\treturn cur >= mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ringGame(self, challenge: List[int]) -> int:\n",
    "        n=len(challenge)\n",
    "        hb=1\n",
    "        for i in range(n):\n",
    "            while  not hb*2>challenge[i]:\n",
    "                hb<<=1\n",
    "        #得到最大bit\n",
    "        me=max(challenge)\n",
    "        def check(x):#判定x是否可以成功遍历数组\n",
    "            if x>=me:\n",
    "                return True\n",
    "            vis=[0]*n\n",
    "            tot=0#总共已经遍历的数\n",
    "            cc=challenge.copy()#复制原数组，因为我们需要进行修改\n",
    "            l=[(i-1)%n for i in range(n)]#等价与链表的pre指针\n",
    "            r=[(i+1)%n for i in range(n)]#等价与链表的nxt指针\n",
    "            def dfs(i,x):\n",
    "                vis[i]=1\n",
    "                cc[i]=x\n",
    "                nonlocal tot\n",
    "                tot+=1\n",
    "                nl=l[i]#当前数pre指针\n",
    "                nr=r[i]#当前数nxt指针\n",
    "                while tot<n:\n",
    "                    f=False\n",
    "                    if cc[nl]<=x:#如果左边可以去，就删除当前数，将分数记在左边\n",
    "                        x|=cc[nl]\n",
    "                        if not vis[nl]:\n",
    "                            tot+=1\n",
    "                        vis[nl]=1\n",
    "                        cc[nl]=x\n",
    "                        l[nr]=nl\n",
    "                        r[nl]=nr\n",
    "                        nl=l[nl]\n",
    "                        f=True\n",
    "                        continue\n",
    "                    if challenge[nr]<=x:#如果右边可以去，就删除当前数，将分数记在左边\n",
    "                        x|=cc[nr]\n",
    "                        if not vis[nr]:tot+=1\n",
    "                        vis[nr]=1\n",
    "                        cc[nr]=x\n",
    "                        l[nr]=nl\n",
    "                        r[nl]=nr\n",
    "                        nr=r[nr]\n",
    "                        f=True\n",
    "                    if not f:\n",
    "                        break\n",
    "            for i,a in enumerate(cc):\n",
    "                if not vis[i] and a<=x:#对i位置开始遍历\n",
    "                    dfs(i,x|a)\n",
    "            return tot==n\n",
    "        cur=hb\n",
    "        hb>>=1\n",
    "        while hb:\n",
    "            if not check(cur+hb-1):#判断这位1需不需要\n",
    "                cur+=hb\n",
    "            hb>>=1\n",
    "        return cur\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ringGame(self, c: List[int]) -> int:\n",
    "        n=len(c)\n",
    "        hb=1\n",
    "        for i in range(n):\n",
    "            while not hb*2>c[i]:\n",
    "                hb<<=1\n",
    "        #得到最大bit\n",
    "        me=max(c)\n",
    "        def check(x):#判定x是否可以成功遍历数组\n",
    "            if x>=me:\n",
    "                return True\n",
    "            vis=[0]*n\n",
    "            tot=0#总共已经遍历的数\n",
    "            cc=c.copy()#复制原数组，因为我们需要进行修改\n",
    "            l=[(i-1)%n for i in range(n)]#等价与链表的pre指针\n",
    "            r=[(i+1)%n for i in range(n)]#等价与链表的nxt指针\n",
    "            def dfs(i,x):\n",
    "                vis[i]=1\n",
    "                cc[i]=x\n",
    "                nonlocal tot\n",
    "                tot+=1\n",
    "                nl=l[i]#当前数pre指针\n",
    "                nr=r[i]#当前数nxt指针\n",
    "                while tot<n:\n",
    "                    f=False\n",
    "                    if cc[nl]<=x:#如果左边可以去，就删除当前数，将分数记在左边\n",
    "                        x|=cc[nl]\n",
    "                        if not vis[nl]:\n",
    "                            tot+=1\n",
    "                        vis[nl]=1\n",
    "                        cc[nl]=x\n",
    "                        l[nr]=nl\n",
    "                        r[nl]=nr\n",
    "                        nl=l[nl]\n",
    "                        f=True\n",
    "                        continue\n",
    "                    if c[nr]<=x:#如果右边可以去，就删除当前数，将分数记在左边\n",
    "                        x|=cc[nr]\n",
    "                        if not vis[nr]:tot+=1\n",
    "                        vis[nr]=1\n",
    "                        cc[nr]=x\n",
    "                        l[nr]=nl\n",
    "                        r[nl]=nr\n",
    "                        nr=r[nr]\n",
    "                        f=True\n",
    "                    if not f:\n",
    "                        break\n",
    "            for i,a in enumerate(cc):\n",
    "                if not vis[i] and a<=x:#对i位置开始遍历\n",
    "                    dfs(i,x|a)\n",
    "            return tot==n\n",
    "        cur=hb\n",
    "        hb>>=1\n",
    "        while hb:\n",
    "            if not check(cur+hb-1):#判断这位1需不需要\n",
    "                cur+=hb\n",
    "            hb>>=1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def ringGame(self, c: List[int]) -> int:\r\n",
    "        n=len(c)\r\n",
    "        hb=1\r\n",
    "        for i in range(n):\r\n",
    "            while not hb*2>c[i]:\r\n",
    "                hb<<=1\r\n",
    "        #得到最大bit\r\n",
    "        me=max(c)\r\n",
    "        def check(x):#判定x是否可以成功遍历数组\r\n",
    "            if x>=me:\r\n",
    "                return True\r\n",
    "            vis=[0]*n\r\n",
    "            tot=0#总共已经遍历的数\r\n",
    "            cc=c.copy()#复制原数组，因为我们需要进行修改\r\n",
    "            l=[(i-1)%n for i in range(n)]#等价与链表的pre指针\r\n",
    "            r=[(i+1)%n for i in range(n)]#等价与链表的nxt指针\r\n",
    "            def dfs(i,x):\r\n",
    "                vis[i]=1\r\n",
    "                cc[i]=x\r\n",
    "                nonlocal tot\r\n",
    "                tot+=1\r\n",
    "                nl=l[i]#当前数pre指针\r\n",
    "                nr=r[i]#当前数nxt指针\r\n",
    "                while tot<n:\r\n",
    "                    f=False\r\n",
    "                    if cc[nl]<=x:#如果左边可以去，就删除当前数，将分数记在左边\r\n",
    "                        x|=cc[nl]\r\n",
    "                        if not vis[nl]:\r\n",
    "                            tot+=1\r\n",
    "                        vis[nl]=1\r\n",
    "                        cc[nl]=x\r\n",
    "                        l[nr]=nl\r\n",
    "                        r[nl]=nr\r\n",
    "                        nl=l[nl]\r\n",
    "                        f=True\r\n",
    "                        continue\r\n",
    "                    if c[nr]<=x:#如果右边可以去，就删除当前数，将分数记在左边\r\n",
    "                        x|=cc[nr]\r\n",
    "                        if not vis[nr]:tot+=1\r\n",
    "                        vis[nr]=1\r\n",
    "                        cc[nr]=x\r\n",
    "                        l[nr]=nl\r\n",
    "                        r[nl]=nr\r\n",
    "                        nr=r[nr]\r\n",
    "                        f=True\r\n",
    "                    if not f:\r\n",
    "                        break\r\n",
    "            for i,a in enumerate(cc):\r\n",
    "                if not vis[i] and a<=x:#对i位置开始遍历\r\n",
    "                    dfs(i,x|a)\r\n",
    "            return tot==n\r\n",
    "        cur=hb\r\n",
    "        hb>>=1\r\n",
    "        while hb:\r\n",
    "            if not check(cur+hb-1):#判断这位1需不需要\r\n",
    "                cur+=hb\r\n",
    "            hb>>=1\r\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ringGame(self, challenge: List[int]) -> int:\n",
    "        n = len(challenge)\n",
    "        bit = 1 << (max(challenge).bit_length() - 1)\n",
    "        challenge = challenge * 3\n",
    "        n3 = n * 3\n",
    "        score_left, index_left = [0] * n3, [0] * n3\n",
    "        for i in range(n3):\n",
    "            score_left[i] = challenge[i]\n",
    "            j = i - 1\n",
    "            while j >= 0 and score_left[j] <= score_left[i]:\n",
    "                score_left[i] |= score_left[j]\n",
    "                j = index_left[j]\n",
    "            index_left[i] = j\n",
    "        score_right, index_right = [0] * n3, [0] * n3\n",
    "        for i in range(n3 - 1, -1, -1):\n",
    "            score_right[i] = challenge[i]\n",
    "            j = i + 1\n",
    "            while j < n3 and score_right[j] <= score_right[i]:\n",
    "                score_right[i] |= score_right[j]\n",
    "                j = index_right[j]\n",
    "            index_right[i] = j\n",
    "\n",
    "        def check(m):\n",
    "            ii = n\n",
    "            while ii < 2 * n:\n",
    "                if challenge[ii] > m:\n",
    "                    ii += 1\n",
    "                    continue\n",
    "                s, l, r = m | score_left[ii] | score_right[ii], index_left[ii], index_right[ii]\n",
    "                while True:\n",
    "                    if r - l > n:\n",
    "                        return True\n",
    "                    if challenge[l] > s and challenge[r] > s:\n",
    "                        break\n",
    "                    if challenge[l] <= s:\n",
    "                        s |= score_left[l]\n",
    "                        l = index_left[l]\n",
    "                    if challenge[r] <= s:\n",
    "                        s |= score_right[r]\n",
    "                        r = index_right[r]\n",
    "                ii = r\n",
    "            return False\n",
    "\n",
    "        ans = bit\n",
    "        while bit:\n",
    "            bit >>= 1\n",
    "            if not check(ans | (bit - 1)):\n",
    "                ans |= bit\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
